package prac6;
/**
 * Unsorted generic list data type implemented as an extension of an 
 * abstract linked list AbstractLList.
 * 
 * @author          Maria Garcia de la Banda
 * @modified        Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
 *                  Brendon Taylor (Feb 2010) - JavaDoc
 *                  Maria (March 2011) - Hierarchy + Interfaces
 * @param           <T> data type used to store the items in each node
 * @since           July 2006
 * @modified        March 2007
 * @modified        March 2011
 * @input           none
 * @output          only for regression testing
 * @errorHandling   none
 * @knownBugs       none
 */

public class UnsortedLinkedList<T> extends LinkedList<T> {
    /**
     * Implements an unsorted linked list iterator.
     *
     * @author          Maria Garcia de la Banda
     * @modified        Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
     *                  Brendon Taylor (Feb 2010) - JavaDoc
     */
    public class UnsortedIterator extends MyIterator {
        /**
         * Adds a new node containing newItem in between current and previous, 
         * setting previous to this new node and leaving current unchanged 
         * Careful resetting head and last, if needed.
         * 
         * @param       newItem to add to the list
         * @complexity  best and worse: O(1) since it is always fixed number of operations
         */
        public void addHere(T newItem) {
            Node temp = new Node(newItem, current);
            if (previous == null) 
                    head = temp;     // reset head if adding at the head
            else
                    previous.successor = temp;
            
            previous = temp;   
            if (current == null)   
                    last = previous; // reset last is adding at the tail
            
            length++;
        }
    }

    /**
     * Creates an empty object of the class, i.e., an empty list of items. 
     * Since the list is implemented with nodes, the size is not needed.
     * 
     * @post        an empty list object is created
     * @complexity  best and worst case: O(1)
     */
    public UnsortedLinkedList() {
	super();
    }

    /**
     * Same as above, but allows the user to provide the size (disregarded). 
     * This method is included to keep the same interface as the List 
     * implemented with arrays.
     * 
     * @param       size of the list (ignored)
     * @see         #UnsortedLList()
     */
    public UnsortedLinkedList(int size) {
	super();
    }

    /**
     * Returns a new unsorted linked list iterator.
     *
     * @see         UnsortedLList#UnsortedLList()
     */
    public UnsortedIterator iterator() {
        return new UnsortedIterator();
    }

    /**
     * Adds a new node (containing the input item) as the head of the list.
     * 
     * @param       newItem to add to the beginning of the list 
     * @post        a new node with item is added as first element
     * @complexity  best and worst case: O(1)
     */
    public void addFirst(T newItem) {
        head = new Node(newItem,head);
        if (last == null) // the list was empty
                    last = head;
        length++;
    }
    
    /**
     * @param       newItem to add to the end of the list 
     * @see         #addLast(Object)
     */
    public void add(T newItem) {
        addLast(newItem);
    }

    /**
     * Adds a new node (containing the input item) as the last of the list.
     *
     * @param       newItem to add to the end of the list 
     * @post        a new node with item is added as last element
     * @complexity  best and worst case: O(1)
     */
    public void addLast(T newItem) {  
        if (last == null) { // list was empty
                last = new Node(newItem,null); 
                head = last;
        }
        else  {
                last.successor = new Node(newItem,null); 
                last = last.successor;
        }
        length++;
    }

    /*********************** REGRESSION TESTING CODE **********************/

    /**
     * Two test cases: empty lists and non-empty lists. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     */
    private static void testIsEmpty() {     
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        System.out.println("TESTING isEmpty()");
        System.out.println("Expected true, got " + myList.isEmpty());
        myList.addFirst(9);
        System.out.println("Expected false, got " + myList.isEmpty());
        myList.addFirst(0);
        System.out.println("Expected false, got " + myList.isEmpty());
        myList.addFirst(1);
        myList.addFirst(2);
        myList.addFirst(14);
        System.out.println("Expected false, got " + myList.isEmpty());
    }

    /**
     * Two test cases: full lists and non-full lists. 
     * Boundary analysis gives three cases: 0 elements, 1, and many (5).
     */
    private static void testIsFull() {      
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        System.out.println("TESTING isFull()");
        System.out.println("Expected false, got " + myList.isFull());
        myList.addFirst(9);
        System.out.println("Expected false, got " + myList.isFull());
        myList.addFirst(0);
        myList.addFirst(1);
        myList.addFirst(2);
        myList.addFirst(14);
        System.out.println("Expected false, got " + myList.isFull());
    }

    /**
     * Two test cases: adding to a full list and to non-full lists. 
     * Boundary analysis gives three cases: 0 elements, 1, and many (5).
     */
    private static void testAddFirst() {    
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        System.out.println("TESTING addFirst()");
        myList.addFirst(9);
        System.out.println("Expected 9, got " + myList);
        myList.addFirst(0);
        System.out.println("Expected 0 9, got " + myList);
        myList.addFirst(1);
        myList.addFirst(14);
        myList.addFirst(20);
        System.out.println("Expected 20 14 1 0 9, got " + myList);
    }

    /**
     * Two test cases: the item is not in the list and it is in it.
     * Subclasses for the class in which the item is in: is the first slot 
     *       the last, or in the middle. 
     * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
     *       used-1, and some slot in the middle.
     * 
     * @throws      Exception thrown when item can not be deleted
     */
    private static void testDeleteItem() throws Exception {         
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        myList.addFirst(8);
        myList.addFirst(7);
        myList.addFirst(5);
        myList.addFirst(5);
        myList.addFirst(4);
        myList.addFirst(3);
        myList.addFirst(2);
        myList.addFirst(1);
        myList.addFirst(0);
        System.out.println("TESTING deleteItem()");
        System.out.println("Expected true, got " + myList.deleteItem(5));
        System.out.println("    with list 0 1 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(1));
        System.out.println("    with list 0 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(0));
        System.out.println("    with list 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(7));
        System.out.println("    with list 2 3 4 5 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(8));
        System.out.println("    with list 2 3 4 5, got " + myList);
        System.out.println("Expected false,  got " + myList.deleteItem(8));
        System.out.println("    with list 2 3 4 5, got " + myList);
    }

    /**
     * Two test cases: the list is empty and it is not. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     * 
     * @throws      Exception thrown when item can not be deleted
     */
    private static void testDeleteFirst() throws Exception {
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        myList.addFirst(4);
        myList.addFirst(3);
        myList.addFirst(2);
        myList.addFirst(1);
        myList.addFirst(0);
        System.out.println("TESTING deleteFirst()");
        System.out.println("Expected 0, got " + myList.deleteFirst());
        System.out.println("    with list 1 2 3 4, got " + myList);
        myList.deleteFirst();
        myList.deleteFirst();
        System.out.println("Expected 3, got " + myList.deleteFirst());
        System.out.println("    with list 4, got " + myList);
        System.out.println("Expected 4, got " + myList.deleteFirst());
        System.out.println("    with list , got " + myList);
        System.out.print("Expected exception ");

        try {
                myList.deleteFirst();
        }
        catch(Exception e) {
                System.out.println(e);
                return;
        }

        System.out.println("but no exception thrown");
    }

    /**
     * Two test cases: the list is empty and it is not. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     * 
     * @throws      Exception thrown when item can not be deleted
     */
    private static void testDeleteLast() throws Exception {         
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        myList.addFirst(4);
        myList.addFirst(3);
        myList.addFirst(2);
        myList.addFirst(1);
        myList.addFirst(0);
        System.out.println("TESTING deleteLast()");
        System.out.println("Expected 4, got " + myList.deleteLast());
        System.out.println("    with list 0 1 2 3, got " + myList);
        myList.deleteLast();
        myList.deleteLast();
        System.out.println("Expected 1, got " + myList.deleteLast());
        System.out.println("    with list 0, got " + myList);
        System.out.println("Expected 0, got " + myList.deleteLast());
        System.out.println("    with list , got " + myList);
        System.out.print("Expected exception ");
        
        try {
                myList.deleteLast();
        }
        catch(Exception e) {
                System.out.println(e);
                return;
        }
        
        System.out.println("but no exception thrown");
    }

    /**
     * Two test cases: the item is not in the list and it is in it. 
     * Subclasses for the class in which the item is in: is the first slot 
     *       the last, or in the middle. 
     * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
     *       used-1, and some slot in the middle.
     */
    private static void testFind() {
        UnsortedLinkedList<Integer> myList = new UnsortedLinkedList<Integer>();
        myList.addFirst(0);
        myList.addFirst(1);
        myList.addFirst(2);
        myList.addFirst(14);
        myList.addFirst(20);
        myList.addFirst(30);
        myList.addFirst(40);
        myList.addFirst(50);
        System.out.println("TESTING find()");
        System.out.println("Expected false, got " + myList.find(9));
        System.out.println("Expected true, got " + myList.find(0));
        System.out.println("Expected true, got " + myList.find(1));
        System.out.println("Expected true, got " + myList.find(14));
        System.out.println("Expected true, got " + myList.find(40));
        System.out.println("Expected true, got " + myList.find(50));
    }
    
    /**
     * @param       args command-line arguments
     */
    public static void main(String[] args) {
        try{   
                testIsEmpty();
                testIsFull();
                testAddFirst();
                testDeleteItem();
                testDeleteFirst();
                testDeleteLast();
                testFind();
        }
        catch (Exception e) {
                System.out.println(" Error, unexpected exception: "+e);
        }
    }
}